/*
 * @lc app=leetcode.cn id=11 lang=cpp
 * @lcpr version=30204
 *
 * [11] 盛最多水的容器
 */

// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution
{
public:
    int maxArea(vector<int> &height)
    {
        // 方法一：双指针，利用题目特性 O(N)
        int i = 0, j = height.size() - 1, res = 0;
        while (i < j)
        {
            // 短板决定接水的高度，当短板不变的情况下，
            // 变长板会导致高度降低或者长度减小，这样都会导致面积减小
            // 因此挪动短板来变化高度，找到面积更大的区域
            res = height[i] < height[j] 
            ? max(res, (j - i) * height[i++]) 
            : max(res, (j - i) * height[j--]);
        }
        return res;
        
        // 方法二： O(N^2) 暴力解法求出每个区间的盛水量
        // int n = height.size();
        // int res = 0;
        // vector<vector<int>> dp(n,vector<int>(n,0));
        // for(int i =0; i < n-1; ++i)
        // {
        //     for(int j = i + 1; j <n; ++j)
        //     {
        //         dp[i][j] = height[i] > height[j] ? (j-i)*height[j] : (j-i)*height[i];
        //         res = max(res, dp[i][j]);
        //     }
        // }
        // return res;
    }
};
// @lc code=end

/*
// @lcpr case=start
// [1,8,6,2,5,4,8,3,7]\n
// @lcpr case=end

// @lcpr case=start
// [1,1]\n
// @lcpr case=end

 */
